
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1868. -- MinCut Query -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1868: MinCut Query</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>37&nbsp;&nbsp;<span class=green>Solved: </span>17<br>[<a href='submitpage.php?id=1868'>Submit</a>][<a href='problemstatus.php?id=1868'>Status</a>][<a href='bbs.php?id=1868'>Discuss</a>]</center><h2>Description</h2><div class=content><div style="text-indent: 28pt"><span style="font-size: 14pt">有</span><i><span style="font-size: 14pt">N</span></i><span style="font-size: 14pt">个点</span><i><span style="font-size: 14pt">M</span></i><span style="font-size: 14pt">条边的无向带权图，求所有</span><i><span style="font-size: 14pt">s,t(s&lt;t)</span></i><span style="font-size: 14pt">，求出</span><i><span style="font-size: 14pt">s</span></i><i><span style="font-size: 14pt">，</span></i><i><span style="font-size: 14pt">t</span></i><span style="font-size: 14pt">的最小割的容量</span><span style="font-size: 14pt">(</span><span style="font-size: 14pt">原题相当于这个意思</span><span style="font-size: 14pt">)</span><span style="font-size: 14pt">。</span></div>
<div style="text-indent: 27.55pt"><b><span style="font-size: 14pt">约束条件</span></b><span style="font-size: 14pt">：</span><span style="font-size: 14pt">&nbsp;</span><span style="font-size: 14pt">数据组数</span><i><span style="font-size: 14pt">T&le;20 , N &le;150, M &le;3000 </span></i></div></div><h2>Input</h2><div class=content></div><h2>Output</h2><div class=content></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>11<br />
24 87<br />
10 20 747794<br />
8 11 760493<br />
10 14 202363<br />
20 3 520060<br />
12 23 180541<br />
19 5 455737<br />
12 9 702568<br />
22 15 21531<br />
15 20 174068<br />
8 18 979803<br />
7 19 133070<br />
16 2 18457<br />
20 11 176230<br />
24 9 898538<br />
15 21 798316<br />
19 6 803527<br />
20 21 759957<br />
10 15 999171<br />
5 2 702306<br />
22 21 336328<br />
9 18 750847<br />
10 2 925858<br />
13 16 819583<br />
10 15 233368<br />
3 21 344044<br />
15 8 426809<br />
13 3 695789<br />
1 4 502652<br />
3 8 999933<br />
13 21 993369<br />
20 5 636227<br />
19 7 297540<br />
4 11 651435<br />
11 12 66602<br />
18 15 573318<br />
13 5 260757<br />
14 9 724287<br />
2 10 429690<br />
5 12 558441<br />
10 16 108118<br />
10 12 834482<br />
12 22 698928<br />
16 17 179498<br />
10 19 276966<br />
11 12 406220<br />
9 17 332872<br />
21 6 409504<br />
12 7 363369<br />
5 12 226341<br />
22 13 700724<br />
3 14 122847<br />
4 2 243556<br />
12 17 537765<br />
21 2 792351<br />
2 5 757035<br />
5 13 324915<br />
12 9 373744<br />
4 12 148366<br />
4 17 151433<br />
24 6 899229<br />
12 24 901475<br />
2 3 794396<br />
6 14 908236<br />
2 3 894429<br />
16 4 335929<br />
10 9 322405<br />
6 3 118607<br />
11 1 670689<br />
10 22 569918<br />
13 21 987744<br />
7 24 298491<br />
12 5 206726<br />
5 7 617506<br />
12 3 469787<br />
22 3 308543<br />
9 14 939508<br />
4 5 376349<br />
12 15 127829<br />
12 16 195747<br />
9 5 755423<br />
24 11 267606<br />
2 14 473731<br />
23 18 229321<br />
9 5 248627<br />
19 18 586709<br />
17 19 213259<br />
21 22 442063<br />
5<br />
8962600<br />
6532036<br />
8433452<br />
3911899<br />
1419379<br />
31 269<br />
3 9 487132<br />
25 31 808934<br />
25 5 370164<br />
24 26 548900<br />
1 30 713774<br />
19 16 187191<br />
23 29 116467<br />
27 30 422091<br />
26 15 855543<br />
1 3 517446<br />
27 6 418419<br />
1 28 103349<br />
5 20 262010<br />
12 10 166343<br />
21 10 319302<br />
17 27 575322<br />
20 21 229905<br />
18 20 73941<br />
30 23 346229<br />
31 1 565985<br />
3 16 789225<br />
28 2 821397<br />
16 21 740085<br />
26 3 207673<br />
2 12 905386<br />
28 4 306641<br />
13 23 340714<br />
22 8 280525<br />
23 4 108582<br />
25 3 937733<br />
19 5 218005<br />
14 31 85274<br />
14 15 247256<br />
22 9 575580<br />
18 11 223206<br />
30 5 962505<br />
26 15 262755<br />
11 5 518945<br />
13 26 723507<br />
7 19 222843<br />
30 4 235190<br />
6 18 849959<br />
13 29 518809<br />
8 17 383304<br />
11 9 999755<br />
13 17 690369<br />
28 16 238047<br />
1 21 66250<br />
26 29 3034<br />
11 6 910254<br />
15 19 519126<br />
30 29 245976<br />
27 23 703730<br />
12 25 253415<br />
13 2 26305<br />
13 14 278051<br />
7 10 308903<br />
11 9 858700<br />
28 1 132003<br />
18 12 144501<br />
6 24 908539<br />
29 20 522536<br />
1 15 171693<br />
10 24 720505<br />
22 6 590965<br />
9 16 495344<br />
14 22 202901<br />
2 1 416950<br />
7 27 717989<br />
12 13 40744<br />
20 17 658391<br />
15 12 553542<br />
6 10 174233<br />
21 20 690361<br />
25 8 266762<br />
1 17 903191<br />
20 28 806368<br />
15 29 730691<br />
18 5 226058<br />
21 14 328206<br />
3 2 947387<br />
5 14 602727<br />
27 20 56553<br />
29 7 528947<br />
24 1 756971<br />
24 30 799632<br />
6 16 418628<br />
9 28 439215<br />
11 14 720091<br />
9 2 909611<br />
16 2 152275<br />
8 4 356621<br />
9 28 77889<br />
20 26 487771<br />
29 22 372261<br />
25 11 107206<br />
8 26 648519<br />
4 5 436874<br />
18 19 967638<br />
17 13 826608<br />
18 6 149315<br />
19 10 591101<br />
16 3 89439<br />
10 31 633075<br />
25 26 933682<br />
2 17 550271<br />
14 24 101840<br />
1 28 92623<br />
29 12 319848<br />
3 28 456683<br />
22 12 745792<br />
16 28 391522<br />
18 12 631492<br />
6 19 359232<br />
29 5 614031<br />
14 10 241082<br />
7 4 33003<br />
1 5 261797<br />
12 19 974581<br />
6 15 513971<br />
15 13 235380<br />
11 19 31537<br />
21 27 433484<br />
6 30 984858<br />
16 27 469912<br />
26 8 505237<br />
15 12 675106<br />
5 12 421245<br />
20 21 519935<br />
7 24 558956<br />
14 5 343769<br />
4 13 552806<br />
10 2 876983<br />
20 8 593094<br />
10 21 186594<br />
5 15 850544<br />
6 30 734714<br />
11 3 474763<br />
18 22 32920<br />
13 27 110295<br />
19 9 760236<br />
7 10 305154<br />
14 19 666329<br />
16 8 306711<br />
14 15 836837<br />
6 17 387091<br />
5 23 714905<br />
15 31 369634<br />
3 16 613074<br />
11 26 419806<br />
9 13 336504<br />
11 20 82196<br />
26 2 721121<br />
9 15 686764<br />
28 26 963982<br />
3 1 539037<br />
26 3 433519<br />
14 18 322533<br />
2 18 627322<br />
12 29 384173<br />
14 6 152041<br />
23 15 307399<br />
10 7 370348<br />
20 26 886060<br />
13 18 626925<br />
13 26 271233<br />
13 26 630444<br />
28 23 875641<br />
15 2 250263<br />
12 6 561042<br />
15 24 208325<br />
27 29 454155<br />
2 1 937458<br />
16 19 591172<br />
22 31 725219<br />
2 10 914654<br />
5 22 53960<br />
7 4 547085<br />
6 29 742699<br />
11 6 798899<br />
4 2 825172<br />
30 8 752507<br />
30 28 178225<br />
15 9 490001<br />
14 7 945054<br />
23 30 671339<br />
14 15 28068<br />
30 21 776788<br />
31 27 292123<br />
8 4 884851<br />
30 7 202255<br />
17 3 973814<br />
6 31 199182<br />
8 14 15721<br />
29 28 590182<br />
21 17 79297<br />
14 30 138723<br />
26 28 230298<br />
9 25 443182<br />
20 1 767058<br />
3 31 860000<br />
18 14 687484<br />
10 19 68978<br />
10 16 895022<br />
4 13 508861<br />
21 7 277686<br />
19 15 590931<br />
14 13 197315<br />
5 1 95821<br />
6 24 395529<br />
3 23 897491<br />
16 20 889619<br />
2 18 80929<br />
23 25 804311<br />
11 29 634226<br />
19 18 543438<br />
8 3 107723<br />
22 14 418658<br />
11 19 689127<br />
17 22 726652<br />
25 24 140529<br />
21 6 241889<br />
23 5 928578<br />
17 28 755200<br />
26 7 126088<br />
16 24 400658<br />
11 31 377018<br />
27 11 918185<br />
14 29 55806<br />
4 11 588955<br />
25 10 19594<br />
28 31 372556<br />
2 4 806446<br />
27 31 560998<br />
31 26 466128<br />
23 5 914694<br />
22 18 987335<br />
9 11 994986<br />
4 24 691762<br />
15 25 631542<br />
19 16 711851<br />
11 10 550400<br />
24 11 801174<br />
21 4 839852<br />
11 4 488264<br />
17 26 570038<br />
1 15 28829<br />
6 23 576988<br />
20 25 578342<br />
30 8 587666<br />
18 27 149518<br />
16 4 41352<br />
9 27 706507<br />
6 14 709365<br />
2 25 434155<br />
21 8 273680<br />
14 8 292539<br />
22 12 916171<br />
9 29 62761<br />
17 27 304466<br />
18 14 713887<br />
1 27 826970<br />
25 5 532622<br />
26 10 637290<br />
28 9 734674<br />
5 29 774549<br />
3 12 704314<br />
17 31 994950<br />
18 9 157794<br />
9<br />
9588156<br />
8400960<br />
8982933<br />
1098823<br />
7323286<br />
3213171<br />
8275358<br />
185677<br />
5040140<br />
6 182<br />
6 3 150324<br />
5 3 409955<br />
4 5 322043<br />
3 2 423920<br />
6 5 293470<br />
3 2 474977<br />
2 6 63134<br />
6 1 161957<br />
2 4 953667<br />
5 3 361730<br />
1 3 88132<br />
6 5 5217<br />
2 5 434574<br />
6 5 276126<br />
6 4 312497<br />
1 4 848154<br />
1 4 843486<br />
1 2 450031<br />
4 6 206899<br />
5 3 406425<br />
2 1 411642<br />
1 5 873481<br />
3 6 628790<br />
5 3 342724<br />
3 2 152494<br />
4 1 124221<br />
6 1 49614<br />
2 1 938271<br />
4 6 96181<br />
2 5 137089<br />
6 1 979970<br />
5 6 800031<br />
2 4 620095<br />
3 1 487331<br />
5 2 231350<br />
2 1 843882<br />
4 3 874134<br />
6 3 623288<br />
4 5 495355<br />
1 3 510140<br />
4 2 677419<br />
6 1 485270<br />
6 5 342734<br />
4 3 654820<br />
2 4 100670<br />
3 6 974803<br />
2 1 598090<br />
1 6 995961<br />
3 2 402558<br />
6 2 418817<br />
1 6 571523<br />
2 6 646580<br />
4 1 273379<br />
4 1 564046<br />
3 2 804900<br />
4 2 721387<br />
2 3 966949<br />
1 3 68507<br />
2 3 665418<br />
3 2 288821<br />
6 3 86318<br />
3 6 419018<br />
2 4 712996<br />
3 6 196296<br />
2 6 264802<br />
6 5 658926<br />
6 3 613092<br />
5 1 255813<br />
1 5 362125<br />
4 2 65187<br />
4 5 56795<br />
5 2 286142<br />
5 6 482438<br />
4 5 263591<br />
6 5 226514<br />
2 1 478258<br />
5 6 352347<br />
6 5 151226<br />
6 3 36422<br />
1 5 340635<br />
1 2 120357<br />
3 4 585473<br />
1 6 568112<br />
6 4 747662<br />
6 3 470217<br />
6 5 335345<br />
5 1 846268<br />
5 6 260758<br />
2 3 194651<br />
1 3 581877<br />
2 3 963954<br />
6 4 41599<br />
6 4 714938<br />
3 1 132541<br />
3 6 720084<br />
1 3 615610<br />
3 5 22940<br />
3 6 2607<br />
5 4 52252<br />
6 4 442531<br />
2 5 953166<br />
6 4 919592<br />
6 2 568485<br />
2 6 804920<br />
3 4 815495<br />
3 4 287640<br />
4 5 851989<br />
1 5 184681<br />
5 1 993019<br />
5 4 754099<br />
6 3 976506<br />
2 5 916067<br />
5 4 571473<br />
5 2 386967<br />
4 5 224548<br />
3 1 581087<br />
1 4 989878<br />
3 4 841198<br />
3 6 162036<br />
6 2 48499<br />
6 5 713862<br />
5 1 570004<br />
4 3 564429<br />
4 2 463634<br />
2 5 880382<br />
1 6 720898<br />
3 6 602409<br />
6 2 852635<br />
5 3 808586<br />
4 6 34987<br />
3 5 237893<br />
1 2 389570<br />
1 6 596367<br />
2 4 222834<br />
5 1 73848<br />
4 3 22301<br />
1 5 960630<br />
4 5 256509<br />
4 3 230776<br />
3 5 253541<br />
3 5 506519<br />
2 3 329500<br />
5 6 33063<br />
2 3 193843<br />
2 1 618835<br />
2 5 95816<br />
5 1 194466<br />
2 1 825362<br />
5 6 705361<br />
5 6 938621<br />
4 2 22925<br />
1 2 387709<br />
1 3 753871<br />
5 2 207467<br />
4 3 472516<br />
6 1 183333<br />
5 1 8694<br />
4 2 632855<br />
3 5 571476<br />
6 1 110752<br />
6 2 14812<br />
4 3 768682<br />
6 2 492500<br />
2 3 314108<br />
1 2 865741<br />
2 4 309588<br />
4 5 458794<br />
6 4 546621<br />
3 2 657372<br />
3 4 49765<br />
2 4 825801<br />
2 5 500336<br />
6 3 617458<br />
1 4 180530<br />
2 3 785293<br />
6 2 792350<br />
2 1 782141<br />
3 4 602256<br />
4 1 172026<br />
5 2 458261<br />
5 3 562958<br />
5 4 232984<br />
1<br />
8078721<br />
27 198<br />
11 24 433879<br />
24 21 219171<br />
18 4 11521<br />
26 14 793661<br />
2 24 912268<br />
8 14 247036<br />
25 12 428609<br />
21 8 59896<br />
6 13 141010<br />
16 9 574888<br />
2 3 794058<br />
19 22 321930<br />
6 8 631943<br />
8 20 544210<br />
23 9 144855<br />
9 25 203760<br />
9 23 341974<br />
5 19 713172<br />
25 13 651900<br />
8 18 257756<br />
25 8 528781<br />
6 27 38321<br />
3 12 506953<br />
22 27 103808<br />
3 22 572526<br />
1 3 190159<br />
23 20 59561<br />
3 4 332974<br />
5 15 263749<br />
22 8 769410<br />
18 19 101833<br />
5 25 239834<br />
14 16 526128<br />
3 10 356632<br />
3 13 848342<br />
27 2 27459<br />
6 24 64902<br />
17 12 40927<br />
4 16 700700<br />
1 7 189563<br />
8 11 42349<br />
5 4 449808<br />
9 25 880570<br />
19 1 415140<br />
20 15 38586<br />
21 19 368543<br />
6 5 241708<br />
14 2 601486<br />
2 4 545191<br />
24 12 710648<br />
24 9 870462<br />
16 8 296631<br />
13 25 845521<br />
14 18 980539<br />
17 11 600931<br />
21 2 658095<br />
3 22 138645<br />
5 24 121785<br />
8 26 376926<br />
22 17 438549<br />
10 13 251531<br />
12 10 97052<br />
14 17 77590<br />
3 27 194873<br />
26 7 632558<br />
3 11 565221<br />
7 23 687006<br />
4 22 580283<br />
12 3 135237<br />
1 25 481885<br />
2 20 792725<br />
27 2 113237<br />
16 22 337243<br />
15 2 386024<br />
22 2 762112<br />
26 20 816261<br />
10 16 149956<br />
22 19 341090<br />
5 3 583959<br />
9 19 265376<br />
11 9 714675<br />
14 8 777378<br />
2 24 917670<br />
9 11 252834<br />
3 21 736907<br />
12 20 483317<br />
5 18 387571<br />
9 12 213487<br />
23 16 946278<br />
23 13 220436<br />
9 23 834947<br />
14 25 150213<br />
21 27 19541<br />
11 8 278675<br />
13 10 728803<br />
18 6 999243<br />
8 10 71162<br />
19 17 484170<br />
23 3 481136<br />
8 24 776181<br />
19 9 785901<br />
17 18 572997<br />
5 23 794115<br />
12 1 784417<br />
10 26 511626<br />
3 16 238503<br />
6 23 352950<br />
5 3 197236<br />
11 25 987800<br />
27 21 31503<br />
25 12 393800<br />
9 17 939014<br />
2 21 503767<br />
17 21 347195<br />
23 3 435777<br />
6 22 837210<br />
26 16 834685<br />
1 20 64836<br />
20 3 679782<br />
3 19 482363<br />
9 16 826265<br />
12 13 506854<br />
22 14 390770<br />
1 20 204106<br />
22 15 951143<br />
26 9 774566<br />
6 7 157266<br />
25 7 203108<br />
2 15 363559<br />
20 17 185161<br />
3 14 895039<br />
14 15 311797<br />
4 9 8431<br />
3 9 295408<br />
22 4 473496<br />
17 18 537968<br />
11 12 760030<br />
20 9 492632<br />
22 27 933008<br />
15 19 101663<br />
26 10 30097<br />
25 24 112111<br />
25 16 803070<br />
11 18 123091<br />
1 12 419370<br />
9 18 127683<br />
10 1 634296<br />
5 10 741188<br />
23 4 62252<br />
4 18 274724<br />
14 4 690627<br />
26 5 418326<br />
9 20 980457<br />
25 20 399827<br />
7 10 43861<br />
5 27 678156<br />
9 25 935696<br />
21 1 997947<br />
27 7 758864<br />
17 22 78409<br />
9 12 159162<br />
13 10 710556<br />
15 7 349145<br />
13 21 928292<br />
9 27 703448<br />
20 4 253682<br />
10 1 315330<br />
24 10 827835<br />
12 25 126902<br />
20 14 217044<br />
14 23 997812<br />
22 24 713257<br />
21 1 615860<br />
12 2 253511<br />
23 10 680298<br />
5 2 971925<br />
2 11 964126<br />
14 6 833556<br />
12 22 782720<br />
14 5 326645<br />
25 15 29730<br />
22 7 443371<br />
11 21 238859<br />
12 18 446287<br />
21 13 873514<br />
11 1 554422<br />
11 5 550659<br />
6 7 374730<br />
11 23 46008<br />
4 3 489211<br />
18 4 502309<br />
13 15 657903<br />
7 11 58107<br />
13 17 655805<br />
25 1 29502<br />
14 17 370449<br />
7 2 871001<br />
14 7 205109<br />
2<br />
2411556<br />
2838287<br />
29 329<br />
29 14 211984<br />
8 22 881424<br />
12 28 594862<br />
18 28 605808<br />
11 13 110912<br />
5 28 565745<br />
19 18 967138<br />
10 3 365761<br />
5 16 189142<br />
1 6 574883<br />
4 26 449834<br />
12 5 343445<br />
1 8 411311<br />
8 17 537284<br />
8 27 835413<br />
4 24 163043<br />
16 13 861121<br />
16 14 946551<br />
1 18 720738<br />
13 19 365915<br />
19 20 900659<br />
15 19 499282<br />
22 28 209119<br />
1 15 524764<br />
27 6 951319<br />
21 3 459971<br />
25 9 452112<br />
9 18 810013<br />
27 5 357056<br />
8 18 478980<br />
13 7 567090<br />
29 13 514996<br />
8 26 874212<br />
24 26 770712<br />
10 16 535327<br />
28 7 946633<br />
25 24 251762<br />
7 3 503442<br />
11 21 992211<br />
27 20 846895<br />
19 24 543484<br />
2 23 378338<br />
3 23 999214<br />
24 17 527999<br />
1 18 358642<br />
12 16 116036<br />
26 3 300132<br />
4 10 480710<br />
19 12 317825<br />
10 1 6072<br />
10 19 728907<br />
16 13 386990<br />
27 15 28657<br />
6 9 313971<br />
2 9 833103<br />
7 1 500839<br />
10 5 802943<br />
19 11 608489<br />
22 21 922597<br />
4 3 500114<br />
11 15 403455<br />
1 22 432111<br />
27 22 262433<br />
28 23 611887<br />
11 14 632905<br />
3 14 486947<br />
7 10 787583<br />
9 3 442044<br />
1 26 747320<br />
22 21 446677<br />
14 21 28216<br />
6 14 79270<br />
28 18 256710<br />
13 21 468233<br />
18 2 313523<br />
2 20 125414<br />
3 20 868265<br />
5 3 376251<br />
22 8 171795<br />
5 7 983805<br />
7 20 199268<br />
29 18 363194<br />
20 8 822255<br />
29 20 376851<br />
12 8 564351<br />
26 1 755149<br />
17 4 217178<br />
17 29 153955<br />
9 14 321699<br />
23 18 452471<br />
1 16 15470<br />
20 8 591441<br />
24 19 121289<br />
17 10 990817<br />
1 21 69028<br />
7 9 693060<br />
3 26 68400<br />
19 5 459968<br />
29 14 120689<br />
9 28 321677<br />
24 28 220240<br />
21 10 328243<br />
7 5 241307<br />
28 13 732494<br />
3 13 786387<br />
5 19 716510<br />
16 21 164627<br />
14 2 482650<br />
12 22 563182<br />
29 13 735659<br />
27 20 510063<br />
29 4 359555<br />
25 28 330335<br />
8 3 324636<br />
12 27 387965<br />
1 2 660704<br />
13 15 1843<br />
7 12 319301<br />
20 13 757447<br />
5 13 33622<br />
12 2 46388<br />
11 1 871044<br />
16 25 969711<br />
12 24 800871<br />
9 6 418418<br />
11 27 268825<br />
13 11 283859<br />
7 9 297894<br />
12 20 875110<br />
1 24 63047<br />
3 7 343703<br />
24 17 800097<br />
12 4 544875<br />
26 7 575261<br />
14 15 84507<br />
20 18 26235<br />
19 1 451353<br />
4 7 659819<br />
29 10 420006<br />
1 2 257693<br />
13 5 392188<br />
27 28 366257<br />
5 2 506749<br />
3 16 366797<br />
9 10 586312<br />
26 2 591003<br />
18 24 879553<br />
16 18 982347<br />
25 2 960251<br />
19 9 517554<br />
1 13 61049<br />
26 15 84149<br />
24 5 293555<br />
11 29 543364<br />
12 6 108343<br />
13 1 891255<br />
12 17 34226<br />
28 18 510828<br />
17 26 28381<br />
10 11 963291<br />
23 18 599301<br />
29 13 513991<br />
25 2 282620<br />
24 21 989694<br />
21 7 661449<br />
21 2 265588<br />
22 24 261903<br />
2 25 733607<br />
27 1 487535<br />
1 19 124047<br />
18 12 757670<br />
23 13 503158<br />
16 24 243659<br />
7 18 565484<br />
13 16 575987<br />
7 13 638369<br />
19 5 251328<br />
22 27 891467<br />
21 24 43634<br />
21 16 191795<br />
6 26 939256<br />
11 19 200708<br />
11 5 744778<br />
26 12 794894<br />
3 16 506458<br />
29 22 999961<br />
10 4 471745<br />
5 25 646712<br />
25 16 552369<br />
8 28 394661<br />
9 25 473288<br />
6 27 106688<br />
23 29 488614<br />
5 25 807125<br />
18 27 874975<br />
24 19 945230<br />
14 20 67661<br />
28 24 536874<br />
3 12 570125<br />
1 11 654946<br />
6 12 948089<br />
8 17 690869<br />
19 10 935501<br />
23 7 552959<br />
18 25 498188<br />
23 15 82200<br />
13 1 619073<br />
7 4 189197<br />
28 15 360495<br />
5 26 308583<br />
4 13 515803<br />
3 12 191615<br />
20 28 615539<br />
18 13 194529<br />
5 9 928546<br />
15 25 547248<br />
29 19 358698<br />
17 8 413003<br />
29 19 816851<br />
13 21 575206<br />
23 3 495192<br />
19 20 484489<br />
3 24 488324<br />
1 5 574359<br />
4 16 279466<br />
21 22 690121<br />
28 13 977623<br />
11 29 90058<br />
17 28 718296<br />
8 3 830541<br />
2 17 803376<br />
24 7 347224<br />
29 1 811559<br />
5 23 259317<br />
29 26 308971<br />
4 17 769973<br />
4 15 903581<br />
14 17 424539<br />
2 5 343900<br />
1 4 627020<br />
20 6 465513<br />
4 21 474918<br />
8 20 849763<br />
28 16 551296<br />
15 8 901555<br />
17 3 922257<br />
3 6 644297<br />
1 11 975430<br />
19 13 779601<br />
14 5 422716<br />
13 21 800836<br />
4 17 575806<br />
15 5 678686<br />
23 15 40882<br />
1 29 228400<br />
3 22 185890<br />
1 21 530608<br />
11 8 816216<br />
15 20 962075<br />
19 28 251305<br />
5 3 6047<br />
24 7 235707<br />
8 29 59766<br />
6 13 554530<br />
1 26 740419<br />
22 10 787378<br />
24 9 119945<br />
10 21 598371<br />
20 19 366027<br />
17 21 372073<br />
3 19 607780<br />
7 3 439260<br />
6 8 417810<br />
19 6 444982<br />
20 6 475738<br />
16 27 638021<br />
7 13 423612<br />
19 22 644816<br />
12 5 691644<br />
17 13 76781<br />
9 7 214108<br />
4 9 162290<br />
4 26 410763<br />
9 18 730117<br />
6 7 306241<br />
24 26 669742<br />
7 25 669539<br />
21 14 267706<br />
25 22 748251<br />
29 5 600868<br />
15 18 386866<br />
23 27 472059<br />
19 25 89326<br />
7 5 812680<br />
6 29 908252<br />
2 1 762698<br />
26 4 870792<br />
11 18 518733<br />
24 19 738996<br />
28 20 594815<br />
25 5 690580<br />
26 19 981338<br />
1 8 682858<br />
5 7 630846<br />
14 12 401426<br />
17 5 841747<br />
6 2 951606<br />
27 4 361874<br />
15 27 4040<br />
1 17 279778<br />
14 12 133131<br />
6 1 980109<br />
25 1 654527<br />
1 27 984241<br />
19 11 207434<br />
19 28 782070<br />
20 25 73371<br />
15 22 575024<br />
28 7 21415<br />
21 29 191006<br />
5 13 625422<br />
15 10 195177<br />
14 5 888681<br />
12 6 795258<br />
17 16 243939<br />
24 5 175680<br />
7 16 836826<br />
12 2 130873<br />
28 29 543848<br />
2<br />
7040077<br />
9847451<br />
19 217<br />
8 5 443438<br />
2 18 449967<br />
19 7 111022<br />
15 14 272670<br />
1 4 517876<br />
8 17 871054<br />
10 12 1926<br />
13 5 545773<br />
12 18 909577<br />
12 16 62427<br />
15 12 466290<br />
12 15 93663<br />
4 10 366333<br />
8 13 524436<br />
11 6 866393<br />
5 19 949223<br />
14 16 897005<br />
15 12 698448<br />
13 18 60909<br />
9 12 126163<br />
2 5 573033<br />
12 16 322903<br />
13 19 138327<br />
5 4 812299<br />
13 11 520499<br />
9 16 583399<br />
12 10 164577<br />
8 2 807879<br />
4 3 419678<br />
3 7 992710<br />
11 19 315613<br />
4 16 970291<br />
8 19 298942<br />
1 8 819440<br />
7 4 919190<br />
18 10 600118<br />
3 11 924348<br />
17 3 801456<br />
8 4 326573<br />
12 6 647340<br />
11 17 819520<br />
4 2 520790<br />
3 1 527250<br />
10 14 705291<br />
10 2 487784<br />
16 17 320789<br />
5 8 353697<br />
4 13 196472<br />
7 1 458925<br />
9 11 714088<br />
6 18 317566<br />
3 2 891335<br />
4 2 280397<br />
3 8 488898<br />
8 15 649293<br />
8 11 926157<br />
10 12 127368<br />
6 13 646387<br />
10 19 491978<br />
2 9 984909<br />
7 11 694997<br />
15 13 467936<br />
16 14 4341<br />
4 5 762387<br />
18 14 8217<br />
7 1 91186<br />
18 8 198953<br />
6 3 268865<br />
1 10 755631<br />
13 16 730763<br />
5 9 198698<br />
1 19 719390<br />
5 2 481777<br />
19 15 489993<br />
6 13 97530<br />
18 5 625381<br />
6 3 302721<br />
10 5 588475<br />
19 5 713081<br />
16 15 477753<br />
3 19 290177<br />
16 1 914399<br />
8 5 940458<br />
19 10 539235<br />
12 8 451504<br />
16 19 733939<br />
11 1 541653<br />
7 3 254733<br />
1 17 248837<br />
3 16 539013<br />
15 13 969763<br />
17 11 358133<br />
18 6 203166<br />
16 13 980438<br />
10 9 714376<br />
6 5 148991<br />
6 19 553147<br />
8 19 682473<br />
2 4 784083<br />
7 8 579959<br />
4 16 454444<br />
18 2 173961<br />
17 13 832039<br />
7 3 546414<br />
12 4 211757<br />
15 4 764903<br />
12 18 166930<br />
3 13 777126<br />
9 17 873436<br />
9 10 844231<br />
8 11 18191<br />
8 14 154914<br />
2 14 350311<br />
4 18 399084<br />
10 7 882410<br />
6 7 846136<br />
4 7 77592<br />
16 18 365724<br />
11 5 906198<br />
1 6 717775<br />
9 10 779466<br />
19 12 29950<br />
14 2 992957<br />
9 16 210802<br />
12 6 218398<br />
15 11 321739<br />
10 15 592009<br />
7 8 639404<br />
10 18 76586<br />
3 19 357999<br />
18 8 690307<br />
3 7 661175<br />
8 17 982354<br />
16 6 218968<br />
6 17 359470<br />
18 12 418447<br />
17 2 573925<br />
19 6 947780<br />
16 15 43726<br />
10 18 17567<br />
14 12 318985<br />
4 15 173202<br />
16 1 908521<br />
18 15 267991<br />
16 7 202789<br />
13 6 776713<br />
9 11 724492<br />
2 3 768217<br />
13 17 950305<br />
11 10 988872<br />
19 2 612982<br />
13 5 460091<br />
14 18 40703<br />
12 16 15534<br />
17 13 960412<br />
12 3 780947<br />
17 9 943990<br />
14 7 863874<br />
3 19 279371<br />
19 7 228786<br />
5 3 13538<br />
7 16 932289<br />
4 7 374772<br />
14 18 359760<br />
1 12 706182<br />
10 4 522002<br />
5 17 507193<br />
7 12 66538<br />
11 14 132348<br />
7 14 107604<br />
6 1 129794<br />
2 9 128426<br />
9 14 684113<br />
4 13 255333<br />
16 5 303316<br />
3 14 658791<br />
9 3 725328<br />
15 6 440877<br />
18 17 548481<br />
4 17 194626<br />
6 3 839404<br />
11 17 523516<br />
14 7 778848<br />
7 12 598515<br />
4 8 730759<br />
14 19 668625<br />
16 15 759634<br />
9 7 315862<br />
8 5 566093<br />
18 8 40216<br />
7 10 186873<br />
6 1 864482<br />
16 12 949154<br />
15 18 147071<br />
6 18 496586<br />
2 12 988540<br />
19 5 722173<br />
2 13 376243<br />
6 7 64092<br />
10 15 462919<br />
1 6 701149<br />
17 7 979246<br />
9 17 36190<br />
5 1 691648<br />
3 7 594216<br />
12 10 165408<br />
16 5 12586<br />
7 6 691976<br />
2 8 453811<br />
17 18 772213<br />
14 15 277487<br />
15 12 647242<br />
13 18 966150<br />
2 3 948481<br />
16 2 427398<br />
8 13 411205<br />
16 7 117185<br />
1<br />
5000093<br />
28 328<br />
25 22 74538<br />
27 14 363102<br />
8 3 640588<br />
2 10 287829<br />
25 6 770331<br />
1 28 718811<br />
25 19 662560<br />
9 14 73765<br />
20 6 707301<br />
28 11 876648<br />
15 7 920965<br />
5 18 888838<br />
2 25 439380<br />
14 10 357510<br />
22 6 71711<br />
12 7 266067<br />
3 15 199089<br />
2 7 358826<br />
24 18 738725<br />
12 25 322270<br />
28 14 727460<br />
1 22 683191<br />
14 4 557052<br />
20 9 628763<br />
15 27 894829<br />
17 14 610269<br />
3 20 485446<br />
28 18 740801<br />
18 14 376427<br />
19 9 64663<br />
28 8 665132<br />
11 9 302121<br />
26 6 324<br />
25 9 147733<br />
27 24 146291<br />
19 24 456376<br />
27 10 838180<br />
9 22 386301<br />
13 11 189498<br />
19 13 924555<br />
21 24 342790<br />
8 7 107682<br />
1 16 490592<br />
24 12 50708<br />
12 11 150255<br />
27 13 353915<br />
10 24 405280<br />
13 4 605357<br />
17 28 995155<br />
15 1 396915<br />
11 18 358699<br />
1 12 138955<br />
16 11 919534<br />
27 2 847846<br />
21 1 438800<br />
6 23 486129<br />
13 10 887990<br />
16 3 676150<br />
27 5 170160<br />
17 20 588724<br />
12 2 866430<br />
14 2 251817<br />
12 1 644147<br />
5 27 87184<br />
22 4 196828<br />
9 21 176738<br />
18 5 561928<br />
11 4 552474<br />
4 2 54526<br />
4 19 16205<br />
15 14 880686<br />
28 11 215547<br />
24 22 461367<br />
2 26 488778<br />
22 20 710873<br />
13 12 527093<br />
11 1 417141<br />
18 11 459132<br />
11 27 70393<br />
8 2 351187<br />
9 28 214780<br />
10 12 536222<br />
25 7 970819<br />
23 21 921753<br />
20 26 753220<br />
20 22 904019<br />
24 4 892984<br />
20 5 91750<br />
3 15 692820<br />
28 7 382705<br />
14 15 750129<br />
14 8 694224<br />
7 16 983158<br />
6 11 744726<br />
2 14 615167<br />
1 18 274957<br />
23 13 417184<br />
18 17 636481<br />
8 3 968967<br />
23 2 469169<br />
24 16 185995<br />
8 13 483779<br />
14 16 206372<br />
24 22 746869<br />
10 24 40585<br />
11 20 238320<br />
23 4 845389<br />
11 20 544208<br />
26 18 419495<br />
27 11 193838<br />
26 13 234661<br />
10 11 486059<br />
14 4 186432<br />
7 9 346277<br />
3 13 160559<br />
6 24 162946<br />
9 25 787892<br />
12 16 961689<br />
4 8 22299<br />
13 20 256959<br />
7 3 743017<br />
3 11 979983<br />
18 26 196229<br />
26 23 39627<br />
11 13 268781<br />
6 26 333577<br />
14 6 870497<br />
2 10 848506<br />
27 25 253125<br />
18 22 270348<br />
20 28 900306<br />
5 2 721064<br />
3 19 760958<br />
19 1 630776<br />
10 23 177504<br />
6 12 403530<br />
22 26 901095<br />
6 11 876700<br />
15 9 49677<br />
19 10 549110<br />
27 14 509193<br />
8 18 619042<br />
12 4 355904<br />
13 22 911192<br />
20 3 550<br />
11 20 126998<br />
12 14 122591<br />
6 3 396297<br />
6 2 743873<br />
14 20 187619<br />
15 2 500844<br />
15 22 942917<br />
28 5 977468<br />
3 1 833429<br />
19 4 517724<br />
12 26 331835<br />
5 10 609340<br />
7 27 220735<br />
19 4 14524<br />
8 1 760183<br />
22 15 728061<br />
21 13 334814<br />
21 12 817858<br />
8 15 938150<br />
16 17 842817<br />
11 28 709362<br />
26 17 457667<br />
9 7 505178<br />
23 10 244945<br />
22 17 726646<br />
25 10 532092<br />
17 14 654125<br />
14 18 744488<br />
27 25 126382<br />
14 24 907527<br />
26 21 406848<br />
26 12 548212<br />
4 17 910311<br />
13 21 286932<br />
13 26 940088<br />
6 18 837656<br />
19 6 586389<br />
8 5 152979<br />
16 3 174070<br />
12 28 554329<br />
2 9 127598<br />
17 6 674885<br />
12 22 243701<br />
14 18 57461<br />
22 3 114219<br />
25 8 219420<br />
1 27 495097<br />
17 18 515261<br />
16 18 661807<br />
9 1 101111<br />
26 14 170115<br />
19 2 117793<br />
23 25 711382<br />
15 11 116331<br />
11 16 672877<br />
5 12 534605<br />
28 24 267403<br />
12 13 210620<br />
1 12 487237<br />
3 20 353645<br />
5 17 750074<br />
16 19 599723<br />
16 13 934452<br />
9 11 180922<br />
19 6 626065<br />
4 10 242672<br />
8 22 868400<br />
10 5 605988<br />
13 17 608415<br />
18 20 566102<br />
10 8 549731<br />
28 7 686897<br />
2 22 168838<br />
17 14 755604<br />
10 5 21009<br />
18 20 595623<br />
10 11 215216<br />
9 4 374884<br />
20 16 589889<br />
14 17 554740<br />
11 27 854195<br />
25 10 174722<br />
2 23 150463<br />
19 24 492801<br />
2 5 350769<br />
19 23 397244<br />
1 16 166830<br />
16 24 443281<br />
7 15 437216<br />
27 12 635873<br />
10 22 909247<br />
1 19 523764<br />
26 4 79146<br />
28 6 26197<br />
28 7 62190<br />
4 9 296836<br />
23 21 5511<br />
12 8 572966<br />
4 15 572484<br />
24 13 161535<br />
16 23 873516<br />
6 7 774510<br />
17 16 67765<br />
22 27 438470<br />
7 27 609525<br />
24 14 667345<br />
7 9 691202<br />
17 20 412661<br />
22 8 722959<br />
25 15 695632<br />
11 2 918122<br />
2 7 244624<br />
12 7 333507<br />
24 12 851585<br />
14 18 808011<br />
10 13 37201<br />
10 3 969101<br />
19 3 737836<br />
7 6 753684<br />
21 5 414866<br />
28 12 359265<br />
11 18 692771<br />
18 2 60708<br />
3 19 868718<br />
24 16 905918<br />
6 2 875018<br />
24 5 129206<br />
15 12 464948<br />
21 28 148633<br />
9 25 533462<br />
15 8 463646<br />
3 2 725395<br />
14 20 765828<br />
5 22 509203<br />
14 18 458318<br />
12 23 445511<br />
5 2 308631<br />
26 1 425787<br />
26 5 812978<br />
18 13 131386<br />
15 27 915710<br />
24 14 475155<br />
7 27 252102<br />
18 15 61992<br />
4 12 911549<br />
17 23 925787<br />
4 12 437272<br />
22 9 740288<br />
8 18 786668<br />
21 7 772933<br />
3 22 846427<br />
16 1 850064<br />
18 7 509318<br />
8 9 368544<br />
19 24 812812<br />
19 25 264390<br />
25 28 598297<br />
16 5 976442<br />
20 13 863771<br />
15 5 408918<br />
23 19 178047<br />
26 6 118451<br />
1 8 988230<br />
27 15 36858<br />
26 5 289889<br />
9 7 721993<br />
27 15 295032<br />
11 14 801285<br />
4 5 699241<br />
27 20 801877<br />
16 26 756932<br />
22 23 963761<br />
28 8 446576<br />
13 6 424774<br />
6 15 509402<br />
7 8 95656<br />
3 18 625674<br />
27 28 53080<br />
11 16 118160<br />
19 14 607583<br />
3 13 326985<br />
18 6 90087<br />
23 17 296010<br />
6<br />
3235673<br />
5937718<br />
1415411<br />
5867970<br />
7383757<br />
9924812<br />
29 89<br />
2 22 940702<br />
18 5 430645<br />
14 26 409560<br />
24 25 224865<br />
4 28 834533<br />
17 25 900258<br />
2 11 56843<br />
25 21 292516<br />
17 10 676838<br />
8 29 983347<br />
4 22 450386<br />
8 10 405691<br />
17 22 244507<br />
4 13 734877<br />
2 13 35880<br />
18 5 459673<br />
20 7 179475<br />
4 7 353348<br />
13 1 910978<br />
4 25 948248<br />
25 20 442571<br />
27 11 367539<br />
13 19 218418<br />
2 26 86682<br />
6 10 50741<br />
11 16 614418<br />
9 26 801056<br />
16 14 477010<br />
8 2 632499<br />
3 21 255289<br />
14 11 56928<br />
15 26 156976<br />
28 10 967488<br />
12 26 745798<br />
22 4 876568<br />
22 29 677623<br />
8 6 670984<br />
19 6 640095<br />
21 7 385038<br />
17 11 78593<br />
26 17 431239<br />
13 20 511560<br />
23 4 779228<br />
3 25 930068<br />
1 25 317429<br />
4 2 335936<br />
4 24 482893<br />
1 8 168165<br />
29 21 275644<br />
5 8 56449<br />
8 5 804742<br />
19 9 757663<br />
17 23 511942<br />
27 26 498981<br />
21 18 408183<br />
19 21 798384<br />
16 17 81199<br />
2 9 520461<br />
29 9 605207<br />
14 29 701747<br />
10 15 973704<br />
10 29 789924<br />
4 8 385372<br />
21 4 910887<br />
9 3 270182<br />
21 17 481765<br />
29 3 176240<br />
9 18 38880<br />
9 16 177162<br />
13 1 888245<br />
25 2 404070<br />
18 12 193909<br />
28 7 495689<br />
13 9 69233<br />
7 9 210981<br />
15 17 411261<br />
18 17 398760<br />
27 17 1512<br />
14 22 497995<br />
6 17 696225<br />
28 27 868157<br />
2 7 346365<br />
6 5 262459<br />
6 2 800554<br />
7 4 862328<br />
15 5 45330<br />
23 14 870020<br />
11 23 941605<br />
24 15 476661<br />
1<br />
3810686<br />
40 0<br />
1<br />
0<br />
40 39<br />
1 2 1<br />
2 3 2<br />
3 4 3<br />
4 5 4<br />
5 6 5<br />
6 7 6<br />
7 8 7<br />
8 9 8<br />
9 10 9<br />
10 11 10<br />
11 12 11<br />
12 13 12<br />
13 14 13<br />
14 15 14<br />
15 16 15<br />
16 17 16<br />
17 18 17<br />
18 19 18<br />
19 20 19<br />
20 21 20<br />
21 22 21<br />
22 23 22<br />
23 24 23<br />
24 25 24<br />
25 26 25<br />
26 27 26<br />
27 28 27<br />
28 29 28<br />
29 30 29<br />
30 31 30<br />
31 32 31<br />
32 33 32<br />
33 34 33<br />
34 35 34<br />
35 36 35<br />
36 37 36<br />
37 38 37<br />
38 39 38<br />
39 40 39<br />
1<br />
20<br />
6 9<br />
1 2 1<br />
1 3 7<br />
2 3 1<br />
2 4 3<br />
2 5 2<br />
3 5 4<br />
4 5 1<br />
4 6 6<br />
5 6 2<br />
1<br />
6<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>276<br />
276<br />
276<br />
248<br />
66<br />
437<br />
374<br />
420<br />
0<br />
212<br />
0<br />
345<br />
0<br />
0<br />
0<br />
0<br />
0<br />
55<br />
175<br />
0<br />
0<br />
27<br />
0<br />
27<br />
27<br />
147<br />
385<br />
780<br />
590<br />
12<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=CodeCraft 2009'>CodeCraft 2009</a></p></div><center>[<a href='submitpage.php?id=1868'>Submit</a>][<a href='problemstatus.php?id=1868'>Status</a>][<a href='bbs.php?id=1868'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
